import collections
import heapq
class Solution(object):
    def minCost(self, maxTime, edges, passingFees):
        n = len(passingFees)
        d = collections.defaultdict(dict)
        for u, v, time in edges:
            if v in d[u]:
                d[u][v] = min(d[u][v], time)
            else:
                d[u][v] = time
            if u in d[v]:
                d[v][u] = min(d[v][u], time)
            else:
                d[v][u] = time
        price = {i: float('inf') for i in range(n)}
        st = [[0, passingFees[0], 0]]
        while st:
            dist, p, id = heapq.heappop(st)
            if p < price[id]:
                price[id] = p
                for v in d[id]:
                    next_dist = dist + d[id][v]
                    next_price = p + passingFees[v]
                    if next_dist <= maxTime and next_price < price[v]:
                        heapq.heappush(st, [next_dist, next_price, v])
        if price[n - 1] == float('inf'):
            return -1
        else:
            return price[n - 1]
                        
data = Solution()
maxTime = 30
edges = [[0,1,10],[1,2,10],[2,5,10],[0,3,1],[3,4,10],[4,5,15]]
passingFees = [5,1,2,20,20,3]
print(data.minCost(maxTime, edges, passingFees))